package bTree;
/**
 * 模拟实现: B树的插入
 */
public class BTree {

    static class BTreeNode {
        public BTreeNode parent ;
        // 关键字结点
        public int[] keys = null;
        // 孩子结点
        public BTreeNode[] children = null;
        // 关键字结点的个数, 用于判断什么时候进行分裂
        public int size;

        public BTreeNode() {
            // 关键字数组
            keys = new int[M];
            children = new BTreeNode[M + 1];
        }
    }

    // 默认是 M 叉树, 并且需要多申请一个结点, 方便进行调整
    public static final int M = 3;
    public BTreeNode root = null; // 根节点

    // 插入一个结点
    public boolean insert(int val) {
        if (root == null) {
            root = new BTreeNode();
            root.keys[0] = val;
            return true;
        }

        // 寻找一下这个值的存在情况
        Pair<BTreeNode, Integer> pair = find(val);
        if (pair.getValue() != -1) {
            // 说明找到了相同的结点
            return false;
        }
        // 否则是处理待插入结点, 获取当前结点
        BTreeNode cur = pair.getKey();
        int i = cur.size - 1;
        // 开始进行插入排序
        for (; i >= 0; i --) {
            if (cur.keys[i] > val) {
                cur.keys[i + 1] = cur.keys[i];
            } else {
                break;
            }
        }
        cur.keys[i + 1] = val;
        cur.size ++; // 元素个数 +1

        // 需要进行分裂
        if (cur.size >= M) {
            split(cur);
            return true;
        } else {
            // 无需分裂
            return true;
        }
    }

    // 分裂
    private void split(BTreeNode cur) {
        BTreeNode parent = cur.parent;

        // 中间的值移动到上面的结点, 中间往右的关键字移动到右边的结点
        int mid = cur.size >> 1;
        int i = mid + 1;

        // 分裂右边
        BTreeNode newNode = new BTreeNode();
        int j = 0;
        for (; i < cur.size; i ++) {
            newNode.keys[j] = cur.keys[i];
            newNode.children[j] = cur.children[i];
            // 再修正父亲结点
            if (newNode.children[j] != null) {
                newNode.children[j].parent = newNode;
            }
            j ++;
        }
        newNode.children[j] = cur.children[i];
        if (newNode.children[j] != null) {
            newNode.children[j].parent = newNode;
        }
        // 再修改分裂后的长度
        newNode.size = j;
        cur.size = cur.size - j - 1;

        // 分裂上边, 如果需要一个新的根节点
        if (cur == root) {
            root = new BTreeNode();
            root.keys[0] = cur.keys[mid];
            root.children[0] = cur;
            root.children[1] = newNode;
            root.size = 1;
            newNode.parent = root;
            cur.parent = root;
            return ;
        }
        newNode.parent = root;

        // 对父亲结点插入 mid 对应的值
        int pIdx = parent.size - 1;
        int midVal = cur.keys[mid];
        for (; pIdx >= 0; pIdx --) {
            if (parent.keys[pIdx] > midVal) {
                parent.keys[pIdx + 1] = parent.keys[pIdx];
                parent.children[pIdx + 2] = parent.children[pIdx + 1];
            } else {
                break;
            }
        }
        parent.keys[pIdx + 1] = midVal;
        parent.children[pIdx + 2] = newNode;
        parent.size ++;

        if (parent.size >= M) {
            split(parent);
        }
    }

    // 寻找这个结点的插入位置
    private Pair<BTreeNode, Integer> find(int val) {
        BTreeNode cur = root;
        BTreeNode parent = null;
        while (cur != null) {
            int i = 0;
            while (i < cur.size) {
                if (cur.keys[i] < val) {
                    i ++;
                } else if (cur.keys[i] == val) {
                    // 返回当前结点的信息
                    return new Pair<>(cur, i);
                } else {
                    break;
                }
            }
            parent = cur;
            cur = cur.children[i];
        }

        // 至此说明 cur 走到空了, Parent 即为待插入结点
        return new Pair<>(parent, -1); // -1 表示走到空了
    }

    public static void main(String[] args) {
        BTree bTree = new BTree();
        int[] array = {53, 139, 75, 49, 145, 36,101};
        for (int i = 0; i < array.length; i++) {
            bTree.insert(array[i]);
        }
        bTree.inorder(bTree.root);
    }

    private void inorder(BTreeNode root){
        if(root == null)
            return;
        for(int i = 0; i < root.size; ++i){
            inorder(root.children[i]);
            System.out.println(root.keys[i]);
        }
        inorder(root.children[root.size]);
    }
}
